#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"

using namespace std;
/*HJJ QQ479287006
 *给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
 
示例 1：
输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-completeness-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


//层次遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

bool isCompleteTree(TreeNode *root) {
    if (!root)
        return true;

    queue<TreeNode *> q;
    q.push(root);
    int flag = false;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        //如果左边空右边不空直接false
        if (!t->left && t->right)
            return false;
        //说明了此时这个队列里面都是叶子节点
        if (!t->right && t->left) {
            if (flag)
                return false;

            q.push(t->left);
            while (!q.empty()) {
                auto item = q.front();
                q.pop();
                if (item->left || item->right)
                    return false;
            }

        } else if (t->right && t->left) {
            if (flag)
                return false;

            //否则加入队列
            q.push(t->left);
            q.push(t->right);
        } else if (!t->right && !t->left) {
            flag = true;//还得判断这种情况 全剩下叶子节点了不能再push 了 push 就出错了
        }


    }

    return true;

}